package leetcode.templates.并查集;

import java.util.Arrays;

public class UnionSet {
}


/**
 * @author ：Shelby Yang
 * @description：TODO
 * @date ：2021-01-27 11:19
 */

//按秩压缩
class UnionFind {
    int[] root;//并查集底层数组
    int[] rank;//节点秩
    int cmpnts;//连通分量个数

    public UnionFind(int n) {
        this.root = new int[n];
        this.rank = new int[n];
        cmpnts = n;
        for (int i = 0; i < n; ++i) {
            root[i] = i;
            this.rank[i] = 1;
        }
    }

    //递归路径压缩的查找
//    public int find(int x) {
//        if (x != root[x]) {
//            root[x] = find(root[x]);
//        }
//        return root[x];
//    }
    //非递归的路径压缩的查找
    int find(int x) {
        int midX, midRoot, rootX;
        //midRoot：为查找x的根节点所经过的中间根节点
        //rootX:x真正的根节点
        // midX:为查找x的根节点所经过的中间节点
        rootX = x;
        while (rootX != root[rootX])   //查找x的根节点
            rootX = root[rootX];      //找到根节点，用rootX记录下
        midX = x;//沿途压缩路径
        while (midX != rootX)          //非递归路径压缩操作
        {
            midRoot = root[midX];      //用midRoot暂存midX的父节点
            root[midX] = rootX;        //root[midX]指向根节点rootX
            midX = midRoot;            //midX移到父节点
        }
        return rootX;         //返回根节点的值
    }


    //按秩优化的合并操作
    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            if (rank[fx] == rank[fy]) {
                root[fx] = fy;
                rank[fy]++;
            } else if (rank[fx] < rank[fy]) {//秩小的指向秩大的
                root[fx] = fy;
            } else {
                root[fy] = fx;
            }
            cmpnts--;
        }
    }

    //检查连通性
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}
//模板2  按节点规模压缩路径
//class UnionFind {
//    int[] parent;
//    int[] size;
//    int n;
//    // 当前连通分量数目
//    int rootCount;
//
//    public UnionFind(int n) {
//        this.n = n;
//        this.rootCount = n;
//        this.parent = new int[n];
//        this.size = new int[n];
//        Arrays.fill(size, 1);
//        for (int i = 0; i < n; ++i) {
//            parent[i] = i;
//        }
//    }
//
//    public int findRoot(int x) {
//        return parent[x] == x ? x : (parent[x] = findRoot(parent[x]));
//    }
//
//    public boolean unite(int x, int y) {
//        x = findRoot(x);
//        y = findRoot(y);
//        if (x == y) {
//            return false;
//        }
//        if (size[x] < size[y]) {
//            int temp = x;
//            x = y;
//            y = temp;
//        }
//        parent[y] = x;
//        size[x] += size[y];
//        --rootCount;
//        return true;
//    }
//
//    public boolean connected(int x, int y) {
//        x = findRoot(x);
//        y = findRoot(y);
//        return x == y;
//    }
//}

